#include <stdio.h>
#include <string.h>
#include "mpi.h"
#include <omp.h>

#define MAX_NUM_OF_CHILDREN     4
#define NUM_OF_CHILDPOINTS      2
#define MAX_NUM_OF_MACHINE      32
#define TRUE                    1
#define FALSE                   0
#define NOCHILD                 -1
#define DUMMY                   -1

struct MPINode {
    int parentsense;
    int childpointers[NUM_OF_CHILDPOINTS]; // rank of children
    int children[MAX_NUM_OF_CHILDREN];
    int parentpointer; // rank of parent
    int flipparent;
};
struct MPINode node;

static int sense = TRUE;
static int rank;
static int num_of_machine;
static int increase = 1;
static int false = 0;
static MPI_Status status;

void init_tree_barrier_mpi(int numm, int rk)
{
    int j;
    num_of_machine = numm;
    rank = rk;
    
    for (j=0; j<MAX_NUM_OF_CHILDREN; ++j) {
        if (4 * rank + j + 1 < num_of_machine)
            node.children[j] = 4 * rank + j + 1;
        else
            node.children[j] = DUMMY;
    }
        
    node.parentpointer = (rank == 0) ? DUMMY : (rank - 1) / 4;
    node.childpointers[0] = (2*rank+1 >= num_of_machine) ? DUMMY : rank * 2 + 1;
    node.childpointers[1] = (2*rank+2 >= num_of_machine) ? DUMMY : rank * 2 + 2;
    node.flipparent = (rank - 1) / 2;
    node.parentsense = FALSE;
}

void tree_barrier_mpi()
{
    int i;
    int recv;

    // repeat until childnotready = {false, false, false, false}
    for (i=0; i<MAX_NUM_OF_CHILDREN; ++i) { 
        if (node.children[i] != DUMMY) {
            MPI_Recv(&recv, 
                     1, 
                     MPI_INT, 
                     node.children[i],
                     MPI_ANY_TAG, 
                     MPI_COMM_WORLD,
                     &status);
        }
    }
    // parentsense^ := false
    if (rank != 0) {
        MPI_Send(&false,
                 1,
                 MPI_INT, 
                 node.parentpointer,
                 1,
                 MPI_COMM_WORLD);
    }
    // if vpid != 0
    //    repeat until parentsense = sense
    if (rank != 0) {
        MPI_Recv(&node.parentsense,
                 1,
                 MPI_INT,
                 node.flipparent,
                 MPI_ANY_TAG,
                 MPI_COMM_WORLD,
                 &status);
    }
}

void release_barrier_mpi()
{   
    int i;
    // childpointers[0]^ := sense
    // childpointers[1]^ := sense
    for (i=0; i<NUM_OF_CHILDPOINTS; ++i) { 
        if (node.childpointers[i] != DUMMY) {
            MPI_Send(&sense,
                     1,
                     MPI_INT,
                     node.childpointers[i],
                     1,
                     MPI_COMM_WORLD);
        }
    }

    // sense := not sense
    sense = 1 - sense;
}

void mpi_tree_barrier()
{
    tree_barrier_mpi();
    release_barrier_mpi();
}
